package com.wtgroup.demo.mianshi.算法.动态规划.背包问题;

/**
 *
 * 5
 * [1, 2, 5]
 * 1 1 1 1 1
 * 1 1 1 2
 * 1 2 2
 * 5
 * @author nisus
 * @version 0.1
 * @since 2023/6/3 15:23
 */
public class D_完全背包 {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int r = D.main(5, coins);
        System.out.println(r);
    }

    static class D {
        static int main(int amount, int[] coins) {
            return func(amount, coins, 0);
        }

        static int func(int rest, int[] coins, int curr) {
            if (rest == 0) {
                return 1;
            }
            if (curr == coins.length) {
                return 0;
            }

            int m = rest / coins[curr];
            int ans = 0;
            for (int i = 0; i <= m; i++) {
                int rest2 = rest - i * coins[curr];
                int r = func(rest2, coins, curr + 1);
                ans += r;
            }

            return ans;
        }
    }


}
